//
//  GenerateTrees.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/21.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  95. 不同的二叉搜索树 II

import UIKit

/*
 95. 不同的二叉搜索树 II
 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

  

 示例：

 输入：3
 输出：
 [
   [1,null,3,2],
   [3,2,null,1],
   [3,1,null,null,2],
   [2,1,3],
   [1,null,2,null,3]
 ]
 解释：
 以上的输出对应以下 5 种不同结构的二叉搜索树：

    1         3     3      2      1
     \       /     /      / \      \
      3     2     1      1   3      2
     /     /       \                 \
    2     1         2                 3
  

 提示：

 0 <= n <= 8
 */

class GenerateTrees: NSObject {
    func generateTrees(_ n: Int) -> [TreeNode?] {
        if n == 0 {
            return []
        }
        return self.generate(1, n)
    }
    
    
    func generate(_ left: Int, _ right: Int) -> [TreeNode?] {
            
        var allTrees = [TreeNode?]()
        
        if left > right {
            //即使没有可用的字数  也要在数组里面加上nil 否则后面70行内层循环就不会执行。
            allTrees.append(nil)
            return allTrees
        }
        
        //枚举所有可以为根的节点
        for i in left ... right{
            //获取所有可行的左子树集合
            let leftTrees = self.generate(left, i-1)
            //获取所有
            let rightTrees = self.generate(i+1, right)
            
            for leftNode in leftTrees {
                for rightNode in rightTrees{
                    let currentNode = TreeNode(i)
                    currentNode.left = leftNode
                    currentNode.right = rightNode
                    allTrees.append(currentNode)
                }
            }
        }
        
        return allTrees
    }
}
